/*
 * Author: 李昀烛 1300012798
 *
 * Outline:
 * 从每一个点开始进行广搜，搜索h步就停止，在搜索的过程中
 * 判断该点与起始点是否在同一个城市，记录其中相同tag最多的k对，
 * 输出即可。复杂度大概是O(num_query * num_person * num_relation)，
 *
 * Optimization:
 * 对于某个地点的所有的人，对其tag数量进行排序，然后依次处理，
 * tag少于第k个答案，就break；对于广搜到的某个人，发现其tag数量
 * 已经小于目前已知的k个答案，就直接跳过。
 *
 * Performance:
 * 最后经过优化，运行10k数据花费1.1s
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

#define BUFF_LIMIT 1000
#define K_LIMIT 20

using namespace std;

unordered_map<string, int> map_person, map_tag, map_organisation;
unordered_map<string, int> map_place_index, map_place_name, map_place_name_level;
unordered_map<int, string> map_person_rev;

queue<int> Q;
vector<int> dis;

string data_path;
int data_size;
string query_file;
string answer_file;

int cnt_person, cnt_tag, cnt_place, cnt_organisation;
char ori[BUFF_LIMIT];

vector<int> place_fa, organisation_location;

vector<vector<int> > relation;
vector<vector<int> > interest;

vector<vector<int> > location, work_place, study_place;

struct Pair
{
    int x, y;
    inline Pair() {} inline Pair(int a, int b)
    { x = a, y = b; }

    inline bool operator < (const Pair tmp) const
    { 
        if(y == tmp.y) return x < tmp.x;
        return y > tmp.y; 
    }
};

set<Pair> visit_list;

struct Tri
{
    int x, y, z;
    inline Tri() {} inline Tri(int a, int b, int c)
    { x = a, y = b, z = c; }

    inline bool operator < (const Tri tmp) const
    {
        if(z == tmp.z)
        {
            if(x == tmp.x) return y < tmp.y;
            return x < tmp.x;
        }

        return z > tmp.z;
    }

    inline bool operator == (const Tri tmp) const
    {
        if(x == tmp.x && y == tmp.y) return true;
        if(x == tmp.y && y == tmp.x) return true;

        return false;
    }
};

struct Ans
{
    Tri result[K_LIMIT + 5];
    int cnt_result;

    inline void init()
    {
        cnt_result = 0;
        for(int i = 1; i < K_LIMIT; i++)
            result[i].z = 0;
    }

    inline void update(Tri buf)
    {
        for(int i = 1; i <= cnt_result; i++)
            if(buf == result[i]) return;

        result[++cnt_result] = buf;

        sort(result + 1, result + cnt_result + 1);
        if(cnt_result > K_LIMIT) cnt_result--;
    }

} ans;

inline void handlePerson()
{
    string person_data_file = data_path + "person.csv";
    FILE *f_person = fopen(person_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_person);

    cnt_person = 0;
    while(fgets(ori, BUFF_LIMIT, f_person))
    {
        char buf[10]; int len_ori = (int)strlen(ori), len_buf = 0;
        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') break;
            buf[len_buf++] = ori[i];
        }

        buf[len_buf] = 0;
        map_person[buf] = ++cnt_person;
    }

    for( unordered_map<string, int>::iterator it = map_person.begin(); it != map_person.end(); it++)
        map_person_rev[it -> second] = it -> first;

    fclose(f_person);
}

inline void handleTag()
{
    string tag_data_file = data_path + "tag.csv";
    FILE *f_tag = fopen(tag_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_tag);

    cnt_tag = 0;
    while(fgets(ori, BUFF_LIMIT, f_tag))
    {
        char buf[10]; int len_ori = (int)strlen(ori), len_buf = 0;
        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') break;
            buf[len_buf++] = ori[i];
        }

        buf[len_buf] = 0;
        map_tag[buf] = ++cnt_tag;
    }

    fclose(f_tag);
}

inline void handlePlace()
{
    string place_data_file = data_path + "place.csv";
    FILE *f_place = fopen(place_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_place);

    cnt_place = 0;
    while(fgets(ori, BUFF_LIMIT, f_place))
    {
        char buf[100]; 
        int len_ori = (int)strlen(ori), len_buf = 0;
        bool check = true;

        string level = ""; 
        int num_level = 0;

        for(int i = 0; i < len_ori - 1; i++)
            if(ori[i] == '|') level = "";
            else level += ori[i];

        if(level == "continent") num_level = 1;
        if(level == "country") num_level = 2;
        if(level == "city") num_level = 3;

        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|')
            {
                buf[len_buf] = 0;

                if(check)
                {
                    map_place_index[buf] = ++cnt_place;
                    len_buf = 0;
                    check = false;
                }
                else
                {
                    if(map_place_name[buf] == 0 || map_place_name_level[buf] > num_level)
                        map_place_name[buf] = cnt_place, map_place_name_level[buf] = num_level;
                    
                    break;
                }
            }
            else
                buf[len_buf++] = ori[i];
        }
    }

    fclose(f_place);
}

inline void handlePartOfPlace()
{
    place_fa.resize(cnt_place + 10);

    string part_of_place_data_file = data_path + "place_isPartOf_place.csv";
    FILE *f_part_of_place = fopen(part_of_place_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_part_of_place);

    while(fgets(ori, BUFF_LIMIT, f_part_of_place))
    {
        char place1[20] = {0}, place2[20] = {0};
        int len_ori = (int)strlen(ori), len_place1 = 0, len_place2 = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') { check = false; continue; }

            if(check)
                place1[len_place1++] = ori[i];
            else
                place2[len_place2++] = ori[i];
        }

        place1[len_place1] = place2[len_place2] = 0;

        place_fa[map_place_index[place1]] = map_place_index[place2];
    }

    fclose(f_part_of_place);
}

inline void handleOrganisation()
{
    string organisation_data_file = data_path + "organisation.csv";
    FILE *f_organisation = fopen(organisation_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_organisation);

    cnt_organisation = 0;
    while(fgets(ori, BUFF_LIMIT, f_organisation))
    {
        char buf[10]; int len_ori = (int)strlen(ori), len_buf = 0;
        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') break;
            buf[len_buf++] = ori[i];
        }

        buf[len_buf] = 0;
        map_organisation[buf] = ++cnt_organisation;
    }

    fclose(f_organisation);
}

inline void handleOrganisationPlace()
{
    organisation_location.resize(cnt_organisation + 10);

    string organisation_locate_data_file = data_path + "organisation_isLocatedIn_place.csv";
    FILE *f_organisation_locate = fopen(organisation_locate_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_organisation_locate);

    while(fgets(ori, BUFF_LIMIT, f_organisation_locate))
    {
        char organisation[20] = {0}, place[20] = {0};
        int len_ori = (int)strlen(ori), len_organisation = 0, len_place = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') { check = false; continue; }

            if(check)
                organisation[len_organisation++] = ori[i];
            else
                place[len_place++] = ori[i];
        }

        organisation[len_organisation] = place[len_place] = 0;

        organisation_location[map_organisation[organisation]] = map_place_index[place];
    }

    fclose(f_organisation_locate);
}

inline void addRelationEdge(int a, int b)
{
    relation[a].push_back(b);
}

inline void handlePersonKnowsPerson()
{
    relation.resize(cnt_person + 10);

    string person_relation_data_file = data_path + "person_knows_person.csv";
    FILE *f_person_relation = fopen(person_relation_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_person_relation);

    while(fgets(ori, BUFF_LIMIT, f_person_relation))
    {
        char person1[20] = {0}, person2[20] = {0};
        int len_ori = (int)strlen(ori), len_person1 = 0, len_person2 = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') { check = false; continue; }

            if(check)
                person1[len_person1++] = ori[i];
            else
                person2[len_person2++] = ori[i];
        }

        person1[len_person1] = person2[len_person2] = 0;

        addRelationEdge(map_person[person1], map_person[person2]);
    }

    fclose(f_person_relation);
}

inline void addInterestEdge(int a, int b)
{
    interest[a].push_back(b);
}

inline void handleInterestingTag()
{
    interest.resize(cnt_person + 10);

    string interesting_tag_data_file = data_path + "person_hasInterest_tag.csv";
    FILE *f_interesting_tag = fopen(interesting_tag_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_interesting_tag);

    while(fgets(ori, BUFF_LIMIT, f_interesting_tag))
    {
        char person[20] = {0}, tag[20] = {0};
        int len_ori = (int)strlen(ori), len_person = 0, len_tag = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') { check = false; continue; }

            if(check)
                person[len_person++] = ori[i];
            else
                tag[len_tag++] = ori[i];
        }

        person[len_person] = tag[len_tag] = 0;

        addInterestEdge(map_person[person], map_tag[tag]);
    }

    fclose(f_interesting_tag);
}

inline void handlePersonLocation()
{
    location.resize(cnt_person + 10);

    string person_location_data_file = data_path + "person_isLocatedIn_place.csv";
    FILE *f_person_location = fopen(person_location_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_person_location);

    while(fgets(ori, BUFF_LIMIT, f_person_location))
    {
        char person[20] = {0}, place[20] = {0};
        int len_ori = (int)strlen(ori), len_person = 0, len_place = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
        {
            if(ori[i] == '|') { check = false; continue; }

            if(check)
                person[len_person++] = ori[i];
            else
                place[len_place++] = ori[i];
        }

        person[len_person] = place[len_place] = 0;

        location[map_person[person]].push_back(map_place_index[place]);
    }

    fclose(f_person_location);
}

inline void handlePersonWorkPlace()
{
    work_place.resize(cnt_person + 10);

    string work_place_data_file = data_path + "person_workAt_organisation.csv";
    FILE *f_work_place = fopen(work_place_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_work_place);

    while(fgets(ori, BUFF_LIMIT, f_work_place))
    {
        char person[20], organisation[20]; 
        int len_ori = (int)strlen(ori), len_person = 0, len_organisation = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
            if(ori[i] == '|')
            {
                if(check)
                {
                    check = false;
                    person[len_person] = 0;
                }
                else
                {
                    organisation[len_organisation] = 0;
                    break;
                }
            }
            else
            {
                if(check)
                    person[len_person++] = ori[i];
                else
                    organisation[len_organisation++] = ori[i];
            }

        work_place[map_person[person]].push_back(organisation_location[map_organisation[organisation]]);
    }

    fclose(f_work_place);
}

inline void handlePersonStudyPlace()
{
    study_place.resize(cnt_person + 10);

    string study_place_data_file = data_path + "person_studyAt_organisation.csv";
    FILE *f_study_place = fopen(study_place_data_file.c_str(), "r");

    fgets(ori, BUFF_LIMIT, f_study_place);

    while(fgets(ori, BUFF_LIMIT, f_study_place))
    {
        char person[20], organisation[20]; 
        int len_ori = (int)strlen(ori), len_person = 0, len_organisation = 0;
        bool check = true;

        for(int i = 0; i < len_ori - 1; i++)
            if(ori[i] == '|')
            {
                if(check)
                {
                    check = false;
                    person[len_person] = 0;
                }
                else
                {
                    organisation[len_organisation] = 0;
                    break;
                }
            }
            else
            {
                if(check)
                    person[len_person++] = ori[i];
                else
                    organisation[len_organisation++] = ori[i];
            }

        study_place[map_person[person]].push_back(organisation_location[map_organisation[organisation]]);
    }

    fclose(f_study_place);
}

inline bool checkPlace(int x, int place_number)
{
    for(int i = 0; i < (int)location[x].size(); i++)
    {
        int now = location[x][i];
        while(now)
        {
            if(now == place_number) return true;
            now = place_fa[now];
        }
    }

    for(int i = 0; i < (int)work_place[x].size(); i++)
    {
        int now = work_place[x][i];
        while(now)
        {
            if(now == place_number) return true;
            now = place_fa[now];
        }
    }
    for(int i = 0; i < (int)study_place[x].size(); i++)
    {
        int now = study_place[x][i];
        while(now)
        {
            if(now == place_number) return true;
            now = place_fa[now];
        }
    }

    return false;
}

inline int checkSimilarity(int x, int y)
{
    int cnt = 0;
    for(int i = 0; i < (int)interest[x].size(); i++)
        for(int j = 0; j < (int)interest[y].size(); j++)
            if(interest[x][i] == interest[y][j]) cnt++;

    return cnt;
}

inline void updAns(int x, int H, int place_number, int K)
{
    dis.resize(cnt_person + 10);
    for(int i = 1; i <= cnt_person; i++) dis[i] = 0;
    Q.push(x), dis[x] = 1;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = 0; i < (int)relation[u].size(); i++)
        {
            int v = relation[u][i];

            if(!dis[v])
            {
                dis[v] = dis[u] + 1;
                if(dis[v] > H + 1) break;

                Q.push(v);
                if((int)interest[v].size() < ans.result[K].z) continue;

                int a = atoi(map_person_rev[x].c_str()), b = atoi(map_person_rev[v].c_str());
                if(checkPlace(v, place_number))
                    ans.update(Tri(min(a, b), max(a, b), checkSimilarity(x, v)));
            }
        }
    }
}

inline void handleQueries()
{
    string query_data_file = query_file;
    FILE *f_query = fopen(query_data_file.c_str(), "r");
    FILE *f_answer = fopen(answer_file.c_str(), "w");

    while(fgets(ori, BUFF_LIMIT, f_query))
    {
        int K, H;
        char place[100];

        sscanf(ori, "%d%d%s", &K, &H, place);

        ans.init();

        int place_number = map_place_name[place];

        visit_list.clear();
        for(int i = 1; i <= cnt_person; i++)
            if(checkPlace(i, place_number)) 
                visit_list.insert(Pair(i, (int)interest[i].size()));

        for(set<Pair>::iterator it = visit_list.begin(); it != visit_list.end(); it++)
        {
            if((int)interest[it -> x].size() < ans.result[K].z) break;
            updAns(it -> x, H, place_number, K);
        }

        for(int i = 1; i < K; i++)
            fprintf(f_answer, "%d|%d ", ans.result[i].x, ans.result[i].y);
        fprintf(f_answer, "%d|%d\n", ans.result[K].x, ans.result[K].y);
    }

    fclose(f_query);
    fclose(f_answer);
}

inline void init(char *argv[])
{
#ifndef LOCAL
    data_path = argv[1];
    data_size = atoi(argv[2]);
    query_file = argv[3];
    answer_file = argv[4];
#else
    data_path = "../../../data/10k-network/";
    data_size = 10000;
    query_file = "../query3.in";
    answer_file = "../query3.out";
#endif
}

int main(int argc, char *argv[]) 
{
    init(argv);

    handlePerson();

    handleTag();

    handlePlace();

    handlePartOfPlace();

    handleOrganisation();

    handleOrganisationPlace();

    handlePersonKnowsPerson();

    handleInterestingTag();

    handlePersonLocation();

    handlePersonWorkPlace();

    handlePersonStudyPlace();

    handleQueries();

    return 0;
}
